home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6815 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.3 KB
  1. Path: solon.com!not-for-mail
  2. From: thads@csn.net (Thad Smith)
  3. Newsgroups: comp.lang.c,comp.lang.c.moderated
  4. Subject: Re: Floating Point arithmetic problem
  5. Date: 15 Feb 1996 07:57:20 -0600
  6. Organization: T3 Systems
  7. Sender: clc@solutions.solon.com
  8. Approved: clc@solutions.solon.com
  9. Message-ID: <4fve40$dli@solutions.solon.com>
  10. References: <c968da6jzm.fsf@damayanti.india.ti.com>
  11. Reply-To: ThadSmith@acm.org
  12. NNTP-Posting-Host: solutions.solon.com
  13.  
  14. In article <c968da6jzm.fsf@damayanti.india.ti.com>,
  15. kuntal@india.ti.com (Kuntal Shah) wrote:
  16. >
  17. >This addition  usually results in  a  few insignificant digits getting
  18. >accumulated in my double variable. For eg.
  19. >
  20. >  f = 12.99  is represented as 12.9900000000000002131628207
  21. >  f = 11.111 is represented as 11.1110000000000006536993169
  22. >
  23. >and so on. I am interested in comparisons with 4 digits precision.
  24. >
  25. >Now coming  to   the  problem. The  insignificant  digits   due to the
  26. >floating  point representation keep  accruing and  there comes a stage
  27. >when the accrued value exceeds 0.0001 which  results in failure of the
  28. >if condition in the  above block of code,  when ideally no such  thing
  29. >should have occurred.
  30.  
  31. You are running into a fundamental problem with floating point
  32. numbers.  Assume that your values have a magnitude of 1e4 (which you
  33. say is the limit).  Assume further that 8-byte IEEE-754 arithmetic is
  34. used.  With approximately 17 digits of precision, the lsb is
  35. approximately 1e-13.  If you add 1e6 numbers and the contributed
  36. rounding error from each addition is 1/2 lsb (a hand-waving, but
  37. probably reasonable sort of assumption), the accumulated error would
  38. be on the order of 5e-8.  That is better than your tolerance of 1e-4.  
  39.  
  40. The retained precision also depends on the order in which the numbers
  41. are added.  The above analysis assumes that the accumulated value
  42. stays less than 1e4.  If, instead, you added 5e5 positive values of
  43. approximately 1e4, THEN 5e5 negative values of opposite value which
  44. result in a theoretical sum near zero, the accumulated value will
  45. temporarily go to approximately 5e9, where the typical 1/2 lsb error
  46. would then be about 5e-9.  Multiply that by 1e6 and get 5e-3, which is
  47. greater than you tolerance.
  48.  
  49. >All I need is a solution that will  overcome this problem. Please
  50. bear
  51. >in mind  that the  loop is executed  millions  of times and  hence any
  52. >costly operation     within  the loop    with  drastically  bring down
  53. >performance.
  54.  
  55. Avoid accumulating large values which will eventually cancel.  See if
  56. your implementation supports a long double type with greater
  57. precision than double.
  58.  
  59. >I have a few options to overcome this problem :-
  60. >
  61. >* After each   addition,   covert  'd' to   an  unsigned   long  after
  62. >  multiplying  by say 1e8, (thus   truncating the unnecessary digits),
  63. >  and divide it by 1e8 to get back the original value.
  64.  
  65. That would, for arbitrary operands, make matters much worse by adding
  66. additional noise.  Your examples, though, suggest that all your values
  67. might be multiples of .001 or .0001.  If that is the case, you would
  68. be much better off scaling your values by a multiplier that results in
  69. all values being integers, i.e., multiplying by 10000, before summing
  70. them.  This will reduce the noise produced when adding the numbers,
  71. probably enough to give you a perfect solution.  Obviously you need to
  72. then divide the final sum by the scaling value to get your intended
  73. sum.
  74.  
  75. Thad
  76.